#include <iostream>

using namespace std;

int maxSubSum(int a[], int startSum, int start, int end)
{
	if(start > end)
		return startSum;

	cout<<"startSum:"<<startSum<<" start:"<<start<<" end:"<<end<<endl;
	int nSum = 0, pSum = 0;
	int i = start;

	while(i <= end && a[i] <=0) nSum += a[i++];
	while(i <= end && a[i] >=0) pSum += a[i++];

	if(startSum + nSum < 0 || pSum + nSum < 0)
	{
		int m = maxSubSum(a, pSum, i, end);
		return startSum > m ? startSum : m;
	}
	else
	{
		startSum = startSum + nSum + pSum;
		return maxSubSum(a, startSum, i, end);
	}
}

int maxS(int a[], int len)
{
	int i = 0;
	while(i < len && a[i] <= 0) i++;
	len--;
	while(len >= i && a[len] <= 0) len--;
	int startSum = 0;
	while(i <= len && a[i] >= 0) startSum += a[i++];
	cout<<"maxS\nstart: "<<i<<"end: "<<len<<endl;
	return maxSubSum(a, startSum, i, len);
}

int main()
{
	int a[9] = {1, -2, 3, 10, -4, 7, 1, 2, -5};
	cout<<"|"<<maxS(a, 9)<<"|"<<endl;
	return 0;
}
